#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;
/*HJJ QQ479287006
 *给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。
示例 1：


输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
vector<vector<int>> ret;
vector<int> path;

void pathSumDfs(TreeNode *root, int targetSum, int sum) {
    if (!root)
        return;

    if (!root->left && !root->right && sum == targetSum) {
        ret.emplace_back(path);
        return;
    }

    if (root->left) {
        path.emplace_back(root->left->val);
        pathSumDfs(root->left, targetSum, sum + root->left->val);
        path.pop_back();
    }

    if (root->right) {
        path.emplace_back(root->right->val);
        pathSumDfs(root->right, targetSum, sum + root->right->val);
        path.pop_back();
    }


}


vector<vector<int>> pathSum(TreeNode *root, int targetSum) {

    if (!root)
        return ret;
    path.emplace_back(root->val);
    pathSumDfs(root, targetSum, root->val);
    return ret;

}